package com.xupt.easy.array;

import java.util.HashMap;

/**
 * @author zhaoxin
 * @title: ContainsNearbyDuplicate219
 * @projectName LeetCode
 * @description: 存在重复元素 II
 * @date 2019/11/19 9:47
 */
public class ContainsNearbyDuplicate219 {


    /**
     * 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。
     *  示例:
     *  输入: nums = [1,2,3,1], k = 3
     *  输出: true
     *
     *  输入: nums = [1,0,1,1], k = 1
     *  输出: true
     *
     *  输入: nums = [1,2,3,1,2,3], k = 2
     *  输出: false
     *
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>(nums.length);

        boolean flag = false;
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])){
                flag = (Math.abs(map.get(nums[i]) - i) <= k);
                if (flag){
                    return true;
                }
            }
            map.put(nums[i], i);
        }


        return false;
    }


    public static void main(String[] args) {
        ContainsNearbyDuplicate219 duplicate219 = new ContainsNearbyDuplicate219();

        int [] arr = {0,1,2,3,4,0,0,7,8,9,10,11,12,0};
        int k = 1;

        duplicate219.containsNearbyDuplicate(arr, k);

    }

}
